package com.shuang.stack2;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        
        //计算两个数组的长度
        int len1 = nums1.length;
        int len2 = nums2.length;

        //用于输出的结果
        int[] res = new int[len1];

        //初始化数组全为-1
        Arrays.fill(res, -1);

        //将nums1数组中的值作为键 下标作为值存到map中用于后续在nums2中找值与其比对
        HashMap<Integer, Integer> nums1Map = new HashMap<>();

        for (int i = 0; i < len1; i++){
            nums1Map.put(nums1[i], i);
        }

        //创建一个栈 作为单调栈（存的是下标） 找右边大的元素 栈从栈顶到栈底为单调递增
        Stack<Integer> stack = new Stack<>();

        //先将第一个下标存到栈顶
        stack.add(0);

        //遍历nums2数组存到单调栈中 三种情况 当前遍历的值与栈顶元素比较  < = >
        for (int i = 1; i < len2; i++){
            if (nums2[i] <= nums2[stack.peek()]){
                //情况一和二
                stack.add(i);
            } else {
                //情况三 要一直比较当前值与栈顶下标对应的值 知道栈为空或者当前值小于栈顶了将当前值再存入栈中
                while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){
                    //当前值大于栈顶元素值的逻辑 ：寻找栈顶下标对应的值是否在nums1数组有，有的话当前遍历到的就是其右边第一个大的元素，存到结果中，将栈顶元素弹出，继续往后比较
                    if (nums1Map.containsKey(nums2[stack.peek()])){
                        //计算存在值的索引位置
                        int index = nums1Map.get(nums2[stack.peek()]);
                        res[index] = nums2[i];
                    }
                    stack.pop();
                }
                //比较完了将该值下标存到栈中
                stack.add(i);
            }
        }

        return res;

    }
}


//精简版
// class Solution {
//     public int[] nextGreaterElement(int[] nums1, int[] nums2) {
//         HashMap<Integer, Integer> map = new HashMap<>();
//         for (int i = 0; i < nums1.length; i++) {
//             map.put(nums1[i], i);
//         }

//         int[] res = new int[nums1.length];
//         Stack<Integer> stack = new Stack<>();
//         Arrays.fill(res, -1);

//         for (int i = 0; i < nums2.length; i++) {
//             while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
//                 int pre = nums2[stack.pop()];
//                 if (map.containsKey(pre)) {
//                     res[map.get(pre)] = nums2[i];
//                 }
//             }
//             stack.push(i);
//         }

//         return res;
//     }
// }